
        <html>
			<head>
			     <title>常见验证码的弱点与验证码识别 - insight-labs</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/141">http://drops.wooyun.org/tips/141</a></h1>
				
      <p>
        <h2>0x00 简介</h2>

<hr />

<p>验证码作为一种辅助安全手段在Web安全中有着特殊的地位，验证码安全和web应用中的众多漏洞相比似乎微不足道，但是千里之堤毁于蚁穴，有些时候如果能绕过验证码，则可以把手动变为自动，对于Web安全检测有很大的帮助。</p>

<p>全自动区分计算机和人类的图灵测试（英语：Completely Automated Public Turing test to tell Computers and Humans Apart，简称CAPTCHA），俗称验证码，是一种区分用户是计算机和人的公共全自动程序。在CAPTCHA测试中，作为服务器的计算机会自动生成一个问题由用户来解答。这个问题可以由计算机生成并评判，但是必须只有人类才能解答。由于计算机无法解答CAPTCHA的问题，所以回答出问题的用户就可以被认为是人类。(from wikipedia)</p>

<p>大部分验证码的设计者都不知道为什么要用到验证码，或者对于如何检验验证码的强度没有任何概念。大多数验证码在实现的时候只是把文字印到背景稍微复杂点的图片上就完事了，程序员没有从根本上了解验证码的设计理念。</p>

<p>验证码的形式多种多样，先介绍最简单的纯文本验证码。</p>

<!--more-->

<h3>纯文本验证码</h3>

<p>纯文本，输出具有固定格式，数量有限，例如：</p>

<pre><code>•1+1=?

•本论坛的域名是?

•今天是星期几?

•复杂点的数学运算
</code></pre>

<p>这种验证码并不符合验证码的定义，因为只有自动生成的问题才能用做验证码，这种文字验证码都是从题库里选择出来的，数量有限。破解方式也很简单，多刷新几次，建立题库和对应的答案，用正则从网页里抓取问题，寻找匹配的答案后破解。也有些用随机生成的数学公式，比如 随机数 [+-*/]随机运算符 随机数=?，小学生水平的程序员也可以搞定……</p>

<p>这种验证码也不是一无是处，对于很多见到表单就来一发的spam bot来说，实在没必要单独为了一个网站下那么大功夫。对于铁了心要在你的网站大量灌水的人，这种验证码和没有一样。</p>

<p>下面讲的是验证码中的重点，图形验证码。</p>

<h3>图形验证码</h3>

<p>先来说一下基础：</p>

<p>识别图形验证码可以说是计算机科学里的一项重要课题，涉及到计算机图形学，机器学习，机器视觉，人工智能等等高深领域……</p>

<p>简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。计算机涉及到的几何图形处理一般有 2维到n维图形处理，边界区分，面积计算，体积计算，扭曲变形校正。对于颜色则有色彩空间的计算与转换，图形上色，阴影，色差处理等等。</p>

<p>在破解验证码中需要用到的知识一般是 像素，线，面等基本2维图形元素的处理和色差分析。常见工具为：</p>

<pre><code>•支持向量机(SVM)

•OpenCV

•图像处理软件(Photoshop,Gimp…)

•Python Image Library
</code></pre>

<p>支持向量机SVM是一个机器学习领域里常用到的分类器，可以对图形进行边界区分，不过需要的背景知识太高深。</p>

<p>OpenCV是一个很常用的计算机图像处理和机器视觉库，一般用于人脸识别，跟踪移动物体等等，对这方面有兴趣的可以研究一下</p>

<p>PS,GIMP就不说了，说多了都是泪啊……</p>

<p>Python Image Library是pyhon里面带的一个图形处理库，功能比较强大，是我们的首选。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270159916.png" alt="20130605190615_98443.png" /></p>

<p>SVM图像边界区分</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270248009.png" alt="20130605192502_65273.png" /></p>

<p>SVM原理，把数据映射到高维空间，然后寻找能够分割的超平面</p>

<p>识别验证码需要充分利用图片中的信息，才能把验证码的文字和背景部分分离，一张典型的jpeg图片，每个像素都可以放在一个5维的空间里，这5个维度分别是，X,Y,R,G,B，也就是像素的坐标和颜色，在计算机图形学中，有很多种色彩空间，最常用的比如RGB，印刷用的CYMK，还有比较少见的HSL或者HSV，每种色彩空间的维度都不一样，但是可以通过公式互相转换。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270273950.png" alt="20130605193040_40334.png" /></p>

<p>RGB色彩空间构成的立方体，每个维度代表一种颜色</p>

<p><img src="http://static.wooyun.org/20131018/2013101809463348968.png" alt="20130605193155_34999.png" /></p>

<p>HSL（色相饱和度）色彩空间构成的锥体，可以参考：</p>

<p><a href="https://zh.wikipedia.org/wiki/HSL%E5%92%8CHSV%E8%89%B2%E5%BD%A9%E7%A9%BA%E9%97%B4">https://zh.wikipedia.org/wiki/HSL%E5%92%8CHSV%E8%89%B2%E5%BD%A9%E7%A9%BA%E9%97%B4</a></p>

<p>了解到色彩空间的原理，就可以用在该空间适用的公式来进行像素的色差判断，比如RGB空间里判断两个点的色差可以用3维空间中两坐标求距离的公式：</p>

<p>distance=sqrt[(r1-r2)^2+(g1-g2)^2+(b1-b2)^2]</p>

<p>更加直观的图片，大家感受一下：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270361306.png" alt="20130605194036_39590.png" /></p>

<p>随便把一张图片的每个像素都映射到RGB色彩空间里就能获得一个这样的立方体。</p>

<p>通过对像素颜色进行统计和区分，可以获得图片的颜色分布，在验证码中，一般来说使用近似颜色最多的像素都是背景，最少的一般为干扰点，干扰线和需要识别文字本身。</p>

<p>对于在RGB空间中不好区分颜色，可以把色彩空间转换为HSV或HSL：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270354489.png" alt="20130605194730_56543.png" /></p>

<h2>0x01 验证码识别的原理和过程</h2>

<hr />

<p>第一步：    二值化</p>

<p>所谓二值化就是把不需要的信息通通去除，比如背景，干扰线，干扰像素等等，只剩下需要识别的文字，让图片变成2进制点阵。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270492372.png" alt="20130605195023_13222.png" /></p>

<p>第二步： 文字分割</p>

<p>为了能识别出字符，需要对要识别的文字图图片进行分割，把每个字符作为单独的一个图片看待。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270469286.png" alt="20130605200952_55267.png" /></p>

<p>第三步：标准化</p>

<p>对于部分特殊的验证码，需要对分割后的图片进行标准化处理，也就是说尽量把每个相同的字符都变成一样的格式，减少随机的程度</p>

<p>最简单的比如旋转还原，复杂点的比如扭曲还原等等</p>

<p>第四步：识别</p>

<p>这一步可以用很多种方法，最简单的就是模板对比，对每个出现过的字符进行处理后把点阵变成字符串，标明是什么字符后，通过字符串对比来判断相似度。</p>

<p>在文章的后半部分会详细解释每步的各种算法</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270485126.png" alt="20130605220655_80781.png" /></p>

<h3>二值化算法</h3>

<p>对于大部分彩色验证码，通过判断色差和像素分布都能准确的把文字和背景分离出来，通过PS等工具把图片打开，用RGB探针对文字和背景图的颜色分别测试，在测试多张图片后，很容易可以发现文字和背景图的RGB差距总是大于一个固定的阈值，即使每次图片的文字和背景颜色都会变化，比如：</p>

<p>新浪和discuz的验证码</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270574022.jpg" alt="20130607213048_17172.jpg" /><img src="http://static.wooyun.org/20131004/2013100410270593853.jpg" alt="20130607213105_77426.jpg" /></p>

<p>通过对文字部分和干扰部分取样可以发现，文字部分的R、G值一般在100左右，B值接近255，但是背景干扰的R、G值则大大高于文字部分，接近200，比较接近文字轮廓部分的像素的RG值也在150以上。通过程序遍历一遍像素就可以完全去掉背景。</p>

<p><img src="http://static.wooyun.org/20131018/2013101809463539011.jpg" alt="20130607213146_11252.jpg" /></p>

<p>Discuz的验证码同理</p>

<p>对于一些和文字颜色相同但是较为分散和单一的干扰像素点，我们可以用判断相邻像素的方法，对于每个点判断该点和相邻8个点的色差，若色差大于某个值，则+1，如果周围有超过6个点的色差都比较大，说明这个点是噪点。对于图像边界的一圈像素，周围没有8个像素，则统统清除，反正文字都在图片的中间位置。</p>

<p>如下图：假如当前像素的坐标是x,y  图形坐标系的原点是图像的左上角</p>

<p><img src="http://static.wooyun.org/20131018/2013101809463533591.jpg" alt="20130607213238_98076.jpg" /></p>

<p>干扰线对于识别验证码增加了一些难度，不过干扰线只有很小的几率会以大角度曲线的方式出现，大部分时间还是小角度直线，去除算法可以参考<a href="http://wenku.baidu.com/view/63bac64f2b160b4e767fcfed.html">http://wenku.baidu.com/view/63bac64f2b160b4e767fcfed.html</a></p>

<p>对于1个像素粗细的干扰线，在字符为2个像素以上的时候，可以用去噪点算法作为滤镜，多执行几次，就可以完美的把细干扰线去掉。</p>

<p>对于像素数比干扰点稍大的干扰色块，可以采用的算法有：</p>

<h3>油漆桶算法（又叫种子填充算法，Floodfill）</h3>

<p>种子填充算法可以方便的计算出任意色块的面积，对于没有粘连字符或者粘连但是字符每个颜色不一样的验证码来说，去除干扰色块的效果很好，你只需要大概计算一下最小的和最大的字符平均占多少像素，然后把这段区间之外像素数的色块排除掉即可。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270648577.gif" alt="Recursive_Flood_Fill_4_%28aka%29.gif" />                    <img src="http://static.wooyun.org/20131004/2013100410270736449.gif" alt="Recursive_Flood_Fill_8_%28aka%29.gif" /></p>

<p>上下左右4个方向填充还有8个方向填充的不同</p>

<p>判断颜色分布：</p>

<p>对于大多数彩色验证码来说，文字基本在图片中心的位置，每个字符本身的颜色是一样的，也就是说对于文字来说，同一种颜色基本都集中在一个固定的区域范围内，通过统计图片中的像素，按近似颜色分组，同时分析每个颜色组在图片中的分布范围，假如说有一种颜色大部分像素都在图片边缘，那么这个颜色肯定不属于要识别的字符，可以去掉。</p>

<p>对于干扰线，并没有一种十分有效的方式能完全去除并且不影响到文字，不过如果能够成功分割字符的话，少量干扰线对于识别率影响不大。</p>

<h3>字符分割算法</h3>

<p>破解验证码的重点和难点就在于能否成功分割字符，这一点也是机器视觉里的一道难题，对物件的识别能力。对于颜色相同又完全粘连的字符，比如google的验证码，目前是没法做到5%以上的识别率的。不过google的验证码基本上人类也只有30%的识别率</p>

<p>对于字符之间完全没有粘连的验证码，比如这个->_-> <img src="http://static.wooyun.org/20131004/2013100410270728767.php" alt="captcha.php" /></p>

<p>分割起来是非常的容易，用最基本的扫描线法就可以分割，比如从最左侧开始从上到下（y=0&#45;--|||||y=n）扫描，如果没有遇到任何文字的像素，就则往右一个像素然后再扫描，如果遇到有文字像素存在，就记录当前横坐标,继续向右扫，突然没有文字像素的时候，就说明到了两个字符直接的空白部分，重复这个步骤再横向扫描就能找到每个字符最边缘4个像素的位置，然后可以用PIL内建的crop功能把单独的字符抠出来。</p>

<p>对于有少许粘连但是只是在字符边角的地方重叠几个像素的验证码，可以用垂直像素直方图的统计方法分割。如下图：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270770745.png" alt="20130607230457_19520.png" /></p>

<p>图上半部分是垂直像素直方图的一种直观展示，假如图片宽度为100像素，则把图片切割为100个1像素的竖线，下面的红色部分为当前x坐标上所有黑色像素的总和。这么一来可以很容易的通过直方图的波峰波谷把4个字母分割开。图片的下半部分是扫描线分隔法，因为干扰线和字符旋转的存在，只有M和5直接才出现了连续的空白部分。</p>

<p>除了垂直像素直方图，还可以从不同的角度进行斜线方向的像素数投影，这种方式对于每次全体字符都随机向一个角度旋转的验证码效果很好。对于每次字符大小和数量都一样的验证码还可以用平均分割法，也就是直接先把中间的文字部分整体切出来，然后按宽度平均分成几份，这种方式对字符粘连比较多用其他方式不好分割的验证码很有用，之前的megaupload的3位字母验证码就是通过这种方式成功分割的。</p>

<p>另外对于彩色的验证码，还可以用颜色分割，比如12306的：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270898817.png" alt="20130607233647_17982.png" /></p>

<p>12306的验证码，每个字符颜色都不一样，真是省事啊。</p>

<p>作为验证码识别里的难点，分割字符还有很多种算法，包括笔画分析曲线角度分析等等，不过即便如此，对粘连的比较厉害的字符还是很难成功的。</p>

<h3>标准化</h3>

<p>标准化的意思是指对于同一个字符，尽可能让每次识别前的样本都一致，以提高识别率。而验证码设计者则会用随机旋转，随机扭曲还有随机字体大小的方式防止字符被简单方法识别。</p>

<p>还原随机旋转的字符一般采用的是旋转卡壳算法：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270830366.png" alt="20130607235719_94258.png" /></p>

<p>此算法非常简单，对一张图片左右各旋转30度的范围，每次1度，旋转后用扫描线法判断字符的宽度，对于标准的长方形字体，在完全垂直的时候肯定是宽度最窄的。嗯？纳尼？上面的图是中间的最窄？好像的确是这样，不过只要每次旋转后的结果都一样，对于识别率不会有影响。</p>

<p>扭曲还原的算法比较蛋疼，效果也不怎么样（其实我不会），不过如果识别算法好的话，对扭曲的字符只要人能认出来，识别率也可以达到接近人类的水准。</p>

<p>还有一些常用到的算法，对于提高识别率和减少样本数量有一定帮助：</p>

<h3>骨架细化：腐蚀算法</h3>

<p><img src="http://static.wooyun.org/20131004/2013100410270978173.png" alt="20130608000722_87311.png" /></p>

<p>腐蚀算法的原理有点像剥洋葱，从最外层沿着最外面的一层像素一圈一圈的去掉，直到里面只剩下一层像素为止。腐蚀算法里面需要用到另一个算法，叫做凸包算法，用来找一堆像素点里面最外围的一层。</p>

<p>最后就是把字符变成统一大小，一般而言是把全部字符都缩到和验证码里出现过的最小的字符一个大小。</p>

<p>详情请自行google……</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270912366.png" alt="20130608001005_74310.png" /></p>

<p>分割算法差不多就到这里了，都是一些比较基础的内容。下面是最终的识别。</p>

<h2>0x02 识别</h2>

<p>其实到了这一步，单独的字符已经分离出来了，可以训练tesseract ocr来识别了，样本数量多的话，识别率也是很高的。不过在这里还是要讲一下，如何自己来实现识别过程。</p>

<p>第一步，样本现在应该已经是一个矩阵的形式了，有像素的地方是1，背景是0，先肉眼识别一下，然后把这个矩阵转换为字符串，建立一个键值对，标明这串字符串是什么字符。之后就只需要多搜集几个同样字符的不同字符串变形，这就是制作模板的过程，。</p>

<p>搜集了足够多的模板后，就可以开始识别了，最简单的方法：汉明距离，但是如果字符有少许扭曲的话，识别率会低的离谱。对比近似字符串用的最多一般是 编辑距离算法(Levenshtein Distance)，具体请自己google。</p>

<p>两种算法的差别在于，对同样两个字符串对比10010101和10101010，汉明距离是6，但是编辑距离是2。</p>

<p>最后一种最NB的识别算法，就是神经网络，神经网络是一种模拟动物神经元工作模式的算法，神经网络有多种不同的结构，但是基本架构分为输入层，隐含层和输出层，输入和输出均为二进制。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410270943161.png" alt="20130608003739_59697.png" /></p>

<p>对于验证码识别来说，输入和输出节点不宜过多，因为多了很慢……所以如果样本矩阵为20x20 400个像素的话，需要对应的也要有400个输入节点，因此我们需要对整个矩阵提取特征值，比如先横向每两个数字XOR一下，然后再竖向每两个数字XOR。</p>

<p>Python有很多封装好的神经网络库，你所需要的只是把特征值输入神经网络，再告诉他你给他的是什么（字符），这样多喂几次之后，也就是训练的过程，随着训练的进行，神经网络的内部结构会改变，逐渐向正确的答案靠拢。神经网络的优势是，对于扭曲的字符识别成功率非常高。另外神经网络在信息安全中还可以起到很多其他作用，比如识别恶意代码等等。</p>

<p>动画验证码</p>

<p>有些不甘寂寞的程序员又玩出了些新花样，比如各种GIF甚至flv格式的动画验证码，下面我来分析一下腾讯安全中心的GIF验证码。</p>

<p><img src="http://static.wooyun.org/20131004/2013100410271083499.gif" alt="20130608005708_49515.gif" /></p>

<p>晃来晃去的看似很难，放慢100倍一帧一帧再看看？</p>

<p><img src="http://static.wooyun.org/20131004/2013100410271023580.gif" alt="20130608010202_83349.gif" /></p>

<p>基本上每帧都有一个字符和其他的分开，用最简单的扫描法就能分割出来。</p>

<p>剩下的就很轻松了，旋转还原之后，先填充内部空白，缩小细化之后做成模板对比，识别率怎么也得有90%了。</p>

<p>原本一张图就能搞定的事情，偏偏给了我们8张图，而且每张图还有一点区别，平白无故增大了很多信息量。</p>

<p>另外就是一些所谓的高用户体验的验证码，比如freebuf的：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410271122654.png" alt="20130608010939_57828.png" /></p>

<p>拖动解锁按钮会触发执行一段js，生成一串随机字符串，ajax给后端程序判断。</p>

<p>破解方式就当留给大家的思考题了，假如我想刷评论的话，怎么办。</p>

<p>还有就是声音验证码的识别，现在很多验证码为了提高用户体验和照顾视觉障碍的用户，都有声音验证码，一般来说是机器生成一段读数字的语音。但是在这方面上很多程序员都偷懒了，预先找了10个数字的声音录音，然后生成的时候把他们随机拼到一起，结果就是这样：</p>

<p><img src="http://static.wooyun.org/20131004/2013100410271119727.png" alt="20130608011512_96225.png" /></p>

<p>前3秒为语音提示，后面的是数字，有没有发现什么？</p>

<p>声音也是可以做成模板的哦</p>

<p>最后就是应该怎么样去设计验证码</p>

<pre><code>•整体效果


•字符数量一定范围内随机


•字体大小一定范围内随机


•波浪扭曲(角度方向一定范围内随机)


•防识别


•不要过度依赖防识别技术


•不要使用过多字符集-用户体验差


•防分割 


•重叠粘连比干扰线效果好


•备用计划


•同样强度完全不同的一套验证码
</code></pre>

<h3>附件添加一个破解验证码的实例包括程序大家自行研究吧：<a href="http://static.wooyun.org/20141017/2014101711073747148.zip">验证码识别</a></h3>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          